package one; /**
 * Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
 * <p>
 * Note:
 * <p>
 * Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
 * The solution set must not contain duplicate triplets.
 * <p>
 * For example, given array S = {-1 0 1 2 -1 -4},
 * <p>
 * A solution set is:
 * (-1, 0, 1)
 * (-1, -1, 2)
 * <p>
 * =======================================================================
 * <p>
 * Complexity : O(n^2)
 * <p>
 * please remember how to avoid the replicate cases
 * 1. in the first loop
 * 2. int the while
 */

import java.util.ArrayList;
import java.util.Arrays;

public class Day01_3Sum {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();

        if (num == null || num.length == 0) {
            return res;
        }

        Arrays.sort(num);

        for (int i = 0; i < num.length - 2; i++) {
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = num.length - 1;
            while (left < right) {
                if (num[left] + num[right] == 0 - num[i]) {
                    ArrayList<Integer> adds = new ArrayList<Integer>();
                    adds.add(num[i]);
                    adds.add(num[left]);
                    adds.add(num[right]);
                    res.add(adds);
                    int tmpl = num[left++];
                    int tmpr = num[right--];
                    while (left <= right && tmpl == num[left] && tmpr == num[right]) {
                        left++;
                        right--;
                    }
                } else if (num[left] + num[right] > 0 - num[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return res;
    }
}
